\n",
" Si c'est votre première visite dans ce TP, lisez attentivement chacun des points détaillé après ce paragraphe.
\n",
" Si vous avez déjà commencer à travailler sur ce TP et que vous souhaiter vous déplacer rapidement dans une partie précise vous pouvez choisir la partie que vous souhaitez rejoindre ci-dessous.
\n",
"Menu de navigation (cliquez pour dérouler)
\n",
" \n",
"
\n",
"
\n",
" La technologie jupyter permet d'exécuter du code python par un simple clique sur Executer ci-dessus.
\n",
" Les morceaux de code de cette page sont interprétées case par case. Pour savoir quelle case a été interprétée avant une autre, il suffit de repérer le numéro devant la case.
\n",
" Une fois qu'une case a été interprétée (=exécutée), la page garde en mémoire les variables et fonctions lues
\n",
" La plateforme propose quelques outils de purge de la mémoire : \n",
"
\n",
" Pour ne pas perdre votre travail pensez à le sauvegarder régulièrement. Par défault, la sauvegarde par un clic sur la disquette en haut à gauche de page, ou par le racourci clavier classique ctrl+S\n",
" est une sauvegarde en local, sur le serveur de jupyter. Vous pouvez et devez très régulièrement sauvegarder votre travail sur votre support personnel de sauvegarde (clef USB, se l'envoyer par mail etc). Ce faisant vous disposerez d'un fichier .ipynb (IPYthon NoteBook) qu'il vous suffira de recharger pour avancer. Après le rechargement assurez vous que les fonctionnalités anciennement developpées et variables utilisées sont bien dans la mémoire de la page (en rééxecutant les cases, ou plus rapidement par Kernel > Restart & Run All.
A NOTER : vous pouvez travailler sur le tp (et tout autre fichier .ipynb) hors connexion en installant une version local du notebook de jupyter. Il faut que votre machine possède un interpreteur de python et que vous soyez connecter à internet.\n", "
pip install jupyterlabjupyter notebook\n",
" Menu de navigation (cliquez pour dérouler)
\n",
" \n",
"
\n",
"
\n",
" Pour apréhender correctement ce TP de cryptologie, revenons sur la notion de chaine de caractères. \n",
"
\n",
" Une chaine de caractère est une variable de type string délimitée par des guillemets simple ou double (touche 3 ou 4) \n",
"
Pour acceder à un caractère on utilise les crochets. Par exemple X[12] permet d'acceder au 13ième caractères. En effet, les caractères sont numérotés à partir de 0.
La fonction len permet de déterminer la longueur d'une chaine
Ecrire une procédure qui prend en paramètre un entier n et une chaine de caractère txt et qui affiche le n-ième caractère de la chaine. La fonction devra afficher un message d'erreur si l'entier n est plus grand que la longueur du texte ou négatif.
A l'aide d'une boucle while affichez un par un les caractères de la chaine X.
Il est possible de parcourir une chaine de caractère à l'aide d'une boucle for : \n",
"
\n",
" for x in X :
\n",
"La variable x prendra successivement comme valeur chacun des caractères de X.\n",
"
L'opération d'addition permet de concatener les chaines de caractères.
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "Y=\"Quelle belle chaine de caractères !\"\n", "Z=X+Y\n", "T=X+\"\\n\"+Y#\\n est le caractère de saut de ligne\n", "print(Z)\n", "print(T)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ecrivez HA HA HA... HA composée de 1983 HA
Informatiquement un caractère est un nombre et tout nombre (inférieur à 1 114 111) est un caractère. On parle du code ASCII du caractère.\n", "
ord prend un caractère et renvoie sa valeur numériquechr prend un nombre (inférieur à 1 114 111) et renvoie son expressionEcrire une fonction qui prend en paramètre une chaine de caractère et qui renvoie la liste des codes ASCII des caractères qui la compose
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def ord_chaine(X) : \n", " return []" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Test\n", "print(ord_chaine(\"Salut\"))\n", "#Résultat : [83, 97, 108, 117, 116]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ecrire une fonction qui prend une liste d'entier correspondant à des codes ASCII et qui renvoie la chaine de caractères de ces codes.
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def chr_chaine(L) : \n", " return \"\"" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Test\n", "print(chr_chaine([67, 97, 32, 115, 101, 32, 112, 97, 115, 115, 101, 32, 98, 105, 101, 110, 32, 63]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ecrire la fonction codex qui prend en paramètre un caractère et renvoie 0 si ce caractère est 'A', 1 si c'est 'B', ..., 25 si c'est 'Z' (sans sensibilité à la case) et -1 sinon
Ecrire la fonction xedoc réalisant l'opération inverse. Si l'entier passé en paramètre n'est pas entre 0 et 25 alors la fonction renverra la chaine ?
\n",
" Menu de navigation (cliquez pour dérouler)
\n",
" \n",
"
\n",
"
Ecrire la fonction Ecesar(txt, clef) qui réalise un chiffrement de César du texte txt avec la clef clef. On utilisera les fonctions codex et xedoc. En particulier si la chaine txt contient des caractères qui ne sont pas reconnu par la fonction codex alors Ecesar renverra la chaine de caractère vide
Ecrire la fonction Dcesar(txt, clef) qui déchiffre un message issu d'un chiffrement de César de clef clef. On prendra les même précaution que précédement.
Dans la variable MESSAGE vous retrouverez le message de l'exercice 5 de la feuille de TD. Réaliser une attaque en brute force et déchiffrez ce message.
\n",
" Menu de navigation (cliquez pour dérouler)
\n",
" \n",
"
\n",
"
Ecrire la fonction Eaffine(txt, clefa, clefb) qui réalise un chiffrement affine du texte txt avec la clef (clefa, clefb). On utilisera les fonctions codex et xedoc. En particulier si la chaine txt contient des caractères qui ne sont pas reconnu par la fonction codex alors Eafine renverra la chaine de caractère vide.
Ecrire la fonction inv_mod(a, n) qui renvoie l'inverse de a modulo n. Si l'inversion n'est pas possible la fonction renvera $0$
Ecrire la fonction Daffine(txt, clefa, clefb) qui réalise un déchiffrement affine.
\n",
" Menu de navigation (cliquez pour dérouler)
\n",
" \n",
"
\n",
"
Comme nous l'avons vu, un caractère est en fait une valeur numérique, mais il existe plusieurs manières de considérer ces nombres. On parle de l'encodage d'un caractère. L'encodage le plus courrant est UTF8 (surtout pour le web) mais il y a également l'ANSI, l'ASCII ou le LATIN1. Les méthodes encode et decode des chaines de caractères permettent de spécifier les encodages. \n",
"
txt.encode(\"...\") va retourner la chaine avec l'encodage spécifié. En particulier cette chaine est une expression binaire qui se repère par un b au début de son expression. Certains caractères, non reconnu par ce navigateur, s'afficherons alors avec leur code binaire, exprimé en hexadécimale, que l'on repère par \\x suivit de deux valeurs héxadécimales.txt.decode(\"...\") va retourner une chaine à partir d'une chaine en binaire en suivant l'encodage spécifié. Mais si les caractères ne sont pas reconnu par l'encodage alors cela provoquera une erreur.\n",
"Ecrire une fonction qui prend en paramètre une chaine de caractère encodée en UTF8 et qui renvoie cette chaine encoder en ANSI
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def modif_encode(txt) : \n", " return txt" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "txt = \"Ma chaîne !\"\n", "print(txt)#Ma chaîne !\n", "print(modif_encode(txt))#Ma chaîne !" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dans la suite nous allons faire du chiffrement de la vie de tous les jours. Dans le cadre actuel, un chiffrement affecte l'expression binaire d'une donnée. On considèrera alors que tous nos messages (c'est à dire les variables d'entrée et de sortie de nos fonctions de chiffrement) seront de telles expressions binaires en suivant l'encodade le plus répandu : utf-8. \n",
"
0x devant son expression."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for n in range(33) : print(n, \"=\", hex(n))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La méthode éponyme, transforme une chaine binaire en hexadécimale
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "X=b'Salut'\n", "print(X.hex())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction bytes.fromhex transforme une chaine exprimée en hexadécimale en binaire.
Ecrire la fonction str2hex qui prend en paramètre une chaine de caractère et renvoie son expression hexadécimale
Ecrire la fonction hex2str réalisant le processus inverse.
\n",
" Menu de navigation (cliquez pour dérouler)
\n",
" \n",
"
\n",
"
Le protocole AES est un peu ardu a expliquer du coté mathématiques de la force : corps fini, groupe de galois, ensemble de permutation, et tout plein d'autre joyeuseté. Par chance, il existe une bibliothèque qui s'occupe de tout ça : cryptography (et pas que de AES, aussi beaucoup d'autre protocole de chiffrement).
Voyons pas à pas comment l'utliser pour réaliser un chiffrement AES.
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Etape 1 : Importer les modules de cette bibliothèque pour réaliser un chiffrement AES." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes\n", "from cryptography.hazmat.backends import default_backend\n", "from cryptography.hazmat.primitives import padding\n", "import os" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Etape 2 : Générer une clef qui faudra conserver et communiquer (très) secretement aux personnes à qui sont destinés les messages cryptés." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "clef = os.urandom(16).hex()#Clef sur 16 octets = 128 bits donner en binaire exprimer en hexadécimale" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(clef)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Etape 3 : Créer un objetCipher (chiffrement en anglais) qui contient en quelque sorte tout le mecanisme permettant de chiffrer (et déchiffrer) avec AES."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"cipher = Cipher(algorithms.AES(bytes.fromhex(clef)), modes.CBC(b\"\\0\"*16), backend=default_backend())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Cet objet de chiffrement (Cipher) prend deux paramètres : le premier est le protocole. Dans notre cas c'est le chiffrement AES avec sa clef (qui doit être exprimée en binaire, d'où l'appel de la fonction bytes.fromhex). Le second est le mode de chiffrement. Celui que nous avons choisi ici est le mode CBC pour Cipher-Block Chaining.\n",
" Il en existe d'autre :\n",
"
CBC, précisément le vecteur nul sur 16 octets : b\"\\0\"*16. Il est possible de mettre n'importe quelle valeur (sur 16 octets) mais dans ce cas, cette valeurs doit également être transmise avec la clef.\n",
"\n", "Pour déchiffrer, c'est la même chose... mais pas dans le même ordre.\n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Données\n", "mess_crypt_hex = '40dd9836ded8feb212d0a40000552320b94f12509f95d6958af70604b919df799cefdee20b9b04861727139647ff731d0e9356459d9896a6346513b39ac7b2555110a2477a13f8750d388c4361b4ea3c'\n", "clef_hex = 'dd19bb5b21dfa8050bad13bb4738a21a'\n", "\n", "#Expression binaire\n", "mess_crypt_bin = bytes.fromhex(mess_crypt_hex)\n", "clef_bin = bytes.fromhex(clef_hex)\n", "\n", "#Objet pour le déchiffrement\n", "cipher = Cipher(algorithms.AES(clef_bin), modes.CBC(b\"\\0\"*16), backend=default_backend())\n", "decrypter = cipher.decryptor()\n", "\n", "#Déchiffrement\n", "mess_decrypt_bin = decrypter.update(mess_crypt_bin) + decrypter.finalize()\n", "\n", "#Suppression de caractère en fin de chaine (qui suivent le remplissage PKCS7 sur 16 octets = 128 bits)\n", "unpadder = padding.PKCS7(128).unpadder()\n", "mess_decrypt_bin = unpadder.update(mess_decrypt_bin) + unpadder.finalize()\n", "\n", "#expression hexadécimale\n", "mess_decrypt_hex=mess_decrypt_bin.hex()\n", "\n", "print(\"Message décrypté en hexadécimal :\", mess_decrypt_hex, end=\"\\n\\n\")\n", "print(\"Message décrypté (pour humain) :\", hex2str(mess_decrypt_hex))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ecrire les fonctions E_AES(message, clef) et D_AES(message, clef) réalisant chiffrement et déchiffrement AES tel que décrit ci-dessus. Les données en entrées et en sorties sont toutes en hexadécimale.
\n",
" Menu de navigation (cliquez pour dérouler)
\n",
" \n",
"
\n",
"
Comme nous l'avons évoquer en cours, utiliser une fonction bijective, c'est crypter. Moralement cela signifie que l'on peut décrypter. Hacher, c'est le même principe : on applique une fonction (injective et non bijective). On obtient ce que l'on appel une empreinte. Dire que la fonction utilisée est injective signifie que si deux messages donnent la même empreinte alors les messages sont nécessairement identique. La différence est qu'il sera (pratiquement) impossible de récupérer le message claire. Le hashage permet par exemple de stocker des mots de passe dans une base de donnée. Il n'est pas nécessaire d'être capable de les décrypter (c'est d'ailleur plus morale de ne pas être capable de les décrypter), il suffit d'être capable de vérifier que le mot de passe saisi a la même empreinte que celle stockée dans la base de donnée.
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Bien que la bibliothèque cryptography permette de gérer quelques protocoles de hachage, la bibliothèque haslib permet la même chose bien plus facilement.
Cette bibliothèque permet d'utiliser de nombreuse fonction de hachage bien connue : \n", "
sha1()sha224()sha256()sha384()sha512()md5()blake2b()blake2s()sha3_224()sha3_256()sha3_384()sha3_512()shake_128()shake_256()f_hash. Alors pour hacher une chaine de caractère txt, exprimée en bianire, on peut faire f_hash(txt).hexdigest(). La méthode hexdigest() permet d'afficher l'empreinte en hexadécimale.\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Réaliser le hachage des chaines salut (deux espaces à la fin) et salut ! (un espace et un point d'exclamation à la fin) correspondant respectivement aux codes héxadécimaux 73616c75742020 et 73616c75742021, en suivant les protocoles sha1, sha256, sha512, md5, sha3_256, sha3_512
Pourquoi tant de fonction différente ? La raison est simple : ces fonctions ne sont pas réellement injective. Elles le sont presque. En effet, on a longtemps pensé par exemple que md5 était une bonne fonction de hashage. Cependant, il a été possible de démontrer qu'il existait une infinité de collision. Une collision c'est lorsque l'on trouve deux messages différents qui ont la même empreinte. Observez une collision avec les deux chaines suivantes après avoir vérifié qu'elles sont bien différentes :
\n",
"d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89 \n",
"55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b \n",
"d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0 \n",
"e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70\n",
"
\n",
"d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89 \n",
"55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b \n",
"d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0 \n",
"e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70\n",
"\n",
" \n",
"
\n",
" Menu de navigation (cliquez pour dérouler)
\n",
" \n",
"
\n",
"
\n",
"La bibliothèque cryptography gère également le protocole de chiffrement RSA.\n",
"
\n",
"La première étape consiste à créer un jeu de clef publique et de clef privé. Pour y arriver, rien de plus simple, il suffit d'utiliser la fonction generate_private_key qui prend en paramètre la puissance que l'on souhaite considérer (en général on met $3$ ou $65537$, c'est une convention dans ce protocole, le chiffrement est alors tout aussi sécurisé et bien rapide). Ainsi que la taille de la clef souhaité, en générale $2048$, mais on peut aussi prendre $4096$ (prend du temps en calcul) ou $1024$ (racourci le temps de calcul mais augmente la vulnérabilité tout comme le $512$ que nous essayerons d'attaquer à la fin de ce TP).\n",
"
\n",
" Il est alors possible de récupérer toutes les données qui permettent de la construction des clefs (voir cours)\n",
"
Ecrire une fonction qui prend en paramètre, $p$, $q$ et $e$ et retourne le $d$ (voir cours)
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def trouve_d(p, q, e) : \n", " return 0" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Test\n", "p=23\n", "q=47\n", "e=3\n", "print(\"d =\", trouve_d(p, q, e))# d = 675" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Générer une clef RSA et vérifier que le $d$ est bien le même que celui trouvé par la fonction précédente.
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour crypter un message : \n",
"
\n",
" PU.encrypt(message, asymmetric.padding.OAEP(mgf=asymmetric.padding.MGF1(algorithm=hashes.SHA1()), algorithm=hashes.SHA1(), label=None))
\n",
" et pour décrypter :
\n",
" PR.decrypt(message, asymmetric.padding.OAEP(mgf=asymmetric.padding.MGF1(algorithm=hashes.SHA1()), algorithm=hashes.SHA1(), label=None))
\n",
" où PU est la clef publique et PR la clef privé et où le message est exprimé en binaire\n",
"
Si vous connaissez une clef publique, vous pouvez créer un objet, au sens de la bibliothèque cryptography pour réaliser un chiffrement.
Pour cela on utilise la fonction RSAPublicNumbers(e, n) qui prend les paramètres de la clef publique. A partir de cette objet, on peux chiffrer comme dans l'exemple suivant. Si le $n$ ou le $e$ ne sont pas bien construit cela provoquera une erreur.
Ecrire une fonction E_RSA(message, n, e) qui prend en paramètre les éléments d'une clef publique et un message en hexadécimal et qui réalise un chiffrement RSA. La valeur de retour est la chaine de caractère chiffré exprimé en hexadécimal.
Inversement, si nous connaissons la clef privé, nous pouvons faire un déchiffrement. De manière duale, on utilise la fonction RSAPrivateNumbers mais cette fonction a besoin de plus que le $n$ et le $d$. Il faut en effet lui passer en paramètre le $p$ et $q$ tel que $n=p\\times q$. Le propriétaire de la clef privé étant le seul a avoir besoin de connaitre ce secret ce n'est pas un problème de sécurité. Il se trouve que cette fonction prend également d'autre paramètre mais ils ne dépendent que de $p$, $q$ et $d$.\n",
"
Ecrire une fonction D_RSA(message, p, q, d) qui prend en paramètre les éléments d'une clef privé et un message en hexadécimal et qui réalise un déchiffrement RSA. La valeur de retour est la chaine de caractère chiffré exprimé en hexadécimal.
Voulez-vous connaitre un terrible secret de prof ? Ma clef publique est
\n",
"\n",
" n= 1510618632668270646714141761954708577877544378205\n",
" 7320975339456471343619842110692441380213747657509282\n",
" 3651759293886518958232115577497523602040649134713228\n",
" 0398515972165561655713266308748142512846066559556799\n",
" 6605379872995602094033482505223280967401296724886969\n",
" 8707157009856428482116212906892906057970523319569243\n",
"\n",
"
\n",
" e = 65537\n",
"
et vous avez appris, petits espions que vous êtes, que $n=p\\times q$ et $p+q$ est compris entre \n",
"\n",
" 2464104660488624191280708373293\n",
" 0419471753688886381369404785220\n",
" 6660120754633373306525629555412\n",
" 4697859073628721712173770897450\n",
" 8169412098556466656647930327021\n",
"\n",
"et\n",
"\n",
" 2464104660488624191280708373293\n",
" 0419471753688886381369404785220\n",
" 6660120754633373306525629555412\n",
" 4697859073628721712173770897450\n",
" 8169412098556466656647943327996\n",
"\n",
"\n",
"Voici le message qu'il vous faut essayer de déchiffrer (si vous le pouvez ... pauvre humain) : \n",
"\n",
" cd82c20ee60d47eb69d5a9f47db6a604\n",
" 254f4414f19ff38dc13a0a79e4353b57\n",
" ec3227d547bf7d00ad4474b8a8b9ddc4\n",
" 72b7f6c90d6b8557515c163a31014e09\n",
" 52c1926fdd6801a53ed40f9ec180a906\n",
" 4cf3a676a341a0b99781652d4b50b2e1\n",
" f3b0c34cdbd0968ab062bcbe90c97a34\n",
" 913907ffa643080ca961bb5ac60e26d1\n",
"\n",
"